|
In graph theory and computer science, the graph sandwich problem is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched" between two other graphs, one of which must be a subgraph and the other of which must be a supergraph of the desired graph. Graph sandwich problems generalize the problem of testing whether a given graph belongs to a family of graphs, and have attracted attention because of their applications and as a natural generalization of recognition problems.〔.〕 ==Problem statement== More precisely, given a vertex set ''V'', a mandatory edge set ''E''1, and a larger edge set ''E''2, a graph ''G'' = (''V'', ''E'') is called a ''sandwich'' graph for the pair ''G''1 = (''V'', ''E''1), ''G''2 = (''V'', ''E''2) if ''E''1 ⊆ ''E'' ⊆ ''E''2. The ''graph sandwich problem'' for property Π is defined as follows:〔.〕〔.〕 :Graph Sandwich Problem for Property Π: :Instance: Vertex set ''V'' and edge sets ''E''1 ⊆ ''E''2 ⊆ ''V'' × ''V''. :Question: Is there a graph ''G'' = (''V'', ''E'') such that ''E''1 ⊆ ''E'' ⊆ ''E''2 and ''G'' satisfies property Π ? The ''recognition problem'' for a class of graphs (those satisfying a property Π) is equivalent to the particular graph sandwich problem where ''E''1 = ''E''2, that is, the optional edge set is empty. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「graph sandwich problem」の詳細全文を読む スポンサード リンク
|